#pragma once
#include <iostream>
namespace test
{
	template<class T>
	struct Node
	{
		T _val;
		Node* _prev = nullptr;
		Node* _next = nullptr;

		Node(const T& x = T())
			:_val(x)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct Iterator
	{
		typedef Iterator Self;
		typedef Node<T> Node;
		Node* _node;
		Iterator(Node* node)
			:_node(node)
		{}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator++(int)
		{
			Iterator tmp(_node);
			_node = _node->_next;
			return tmp;
		}

		Self operator--(int)
		{
			Iterator tmp(_node);
			_node = _node->_prev;
			return tmp;
		}

		Ref operator*()
		{
			return _node->_val;
		}

		Ptr operator->()
		{
			return &_node->_val;
		}

		bool operator==(const Self& tmp)
		{
			return _node == tmp._node;
		}

		bool operator!=(const Self& tmp)
		{
			return _node != tmp._node;
		}
	};

	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator Self;
		Iterator _it;

		Reverse_iterator(Iterator it)
			:_it(it)
		{}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self operator++(int)
		{
			return _it--;
		}

		Self operator--(int)
		{
			return _it++;
		}

		Ref operator*()
		{
			return *_it;
		}

		Ptr operator->()
		{
			return _it.operator->();
		}

		bool operator==(const Self& tmp)
		{
			return _it == tmp._it;
		}
		bool operator!=(const Self& tmp)
		{
			return _it != tmp._it;
		}
	};

	template<class T>
	class List
	{
	public:
		typedef Iterator<T, T&, T*> iterator;
		typedef Iterator<T, const T&, const T*> const_iterator;
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
		typedef Node<T> Node;

		reverse_iterator rbegin()
		{
			return --end();
		}

		reverse_iterator rend()
		{
			return end();
		}

		const_reverse_iterator rbegin() const
		{
			return --end();
		}

		const_reverse_iterator rend() const
		{
			return begin();
		}


		const_iterator begin() const
		{
			return _head->_next;
		}

		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}

		
		const_iterator end() const
		{
			return _head;
		}

		List()
		{
			init();
		}

		List(const List& tmp)
		{
			init();
			for (auto x : tmp)
			{
				push_back(x);
			}
		}

		List& operator=(List tmp)
		{
			std::swap(_head, tmp._head);
			return *this;
		}

		void init()
		{
			_head = new Node;
			_head->_next = _head->_prev = _head;
		}

		void destroy()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(val);
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			prev->_next = newnode;
			return newnode;
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return next;
		}

		void push_back(const T& val)
		{
			insert(end(), val);
		}

		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		~List()
		{
			destroy();
			delete _head;
			_head = nullptr;
		}
	private:
		Node* _head;
	};
}
